/* @description:Nginx 对基数树的封装
 *
 *
 *
 *
 * Copyright (C) Igor Sysoev
 * Copyright (C) Nginx, Inc.
 */


#ifndef _NGX_RADIX_TREE_H_INCLUDED_
#define _NGX_RADIX_TREE_H_INCLUDED_


#include <ngx_config.h>
#include <ngx_core.h>


#define NGX_RADIX_NO_VALUE   (uintptr_t) -1

typedef struct ngx_radix_node_s  ngx_radix_node_t;

/*
 *@brief:nginx 基数树的节点结构定义
 *
 */
struct ngx_radix_node_s {
    ngx_radix_node_t  *right; //右子树;
    ngx_radix_node_t  *left;  //左子树;
    ngx_radix_node_t  *parent; //父节点;
    uintptr_t          value; //节点存的值;
};


/*
 *@brief:Nginx中基数树的上下文定义
 *
 */
typedef struct {
    ngx_radix_node_t  *root;  //root根节点
    ngx_pool_t        *pool;  //基数树所在的内存池
    ngx_radix_node_t  *free;  //空闲节点;
    char              *start;
    size_t             size; //基数树的节点个数;
} ngx_radix_tree_t;


//创建基数树;
ngx_radix_tree_t *ngx_radix_tree_create(ngx_pool_t *pool, ngx_int_t preallocate);

//插入基数树;
ngx_int_t ngx_radix32tree_insert(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask, uintptr_t value);

//删除基数树;
ngx_int_t ngx_radix32tree_delete(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask);
//查找
uintptr_t ngx_radix32tree_find(ngx_radix_tree_t *tree, uint32_t key);

#if (NGX_HAVE_INET6)
ngx_int_t ngx_radix128tree_insert(ngx_radix_tree_t *tree, u_char *key, u_char *mask, uintptr_t value);
ngx_int_t ngx_radix128tree_delete(ngx_radix_tree_t *tree, u_char *key, u_char *mask);
uintptr_t ngx_radix128tree_find(ngx_radix_tree_t *tree, u_char *key);
#endif


#endif /* _NGX_RADIX_TREE_H_INCLUDED_ */
